package main

func main() {
	
}
//#link: https://leetcode-cn.com/problems/majority-element-ii/
func majorityElement(nums []int)(ans []int) {
	tempMap:=make(map[int]int)
	for _,num:=range nums{
		tempMap[num]++
	}
	targetCount:=len(nums)/3
	for key,value:=range tempMap{
		if value>targetCount{
			ans = append(ans, key)
		}
	}
	return ans
}

func way2(nums []int)(ans []int) {
	targetCount:=len(nums)/3
	tempMap:=make(map[int]int)
	for _,num:=range nums{
		if tempMap[num]==-1{
			continue
		}
		tempMap[num]++
		if tempMap[num]>targetCount{
			ans = append(ans, num)
			tempMap[num]=-1
		}
	}

	return ans
}

/**
 * @Description: 摩尔投票法,消除不同的 剩下的就是超过 1/3 的
 * @param nums
 */
func way3(nums []int)  {
	var element func([]int)[]int
	element=func(nums []int) (ans []int) {
		element1, element2 := 0, 0
		vote1, vote2 := 0, 0

		for _, num := range nums {
			if vote1 > 0 && num == element1 { // 如果该元素为第一个元素，则计数加1
				vote1++
			} else if vote2 > 0 && num == element2 { // 如果该元素为第二个元素，则计数加1
				vote2++
			} else if vote1 == 0 { // 选择第一个元素
				element1 = num
				vote1++
			} else if vote2 == 0 { // 选择第二个元素
				element2 = num
				vote2++
			} else { // 如果三个元素均不相同，则相互抵消1次
				vote1--
				vote2--
			}
		}

		cnt1, cnt2 := 0, 0
		for _, num := range nums {
			if vote1 > 0 && num == element1 {
				cnt1++
			}
			if vote2 > 0 && num == element2 {
				cnt2++
			}
		}

		// 检测元素出现的次数是否满足要求
		if vote1 > 0 && cnt1 > len(nums)/3 {
			ans = append(ans, element1)
		}
		if vote2 > 0 && cnt2 > len(nums)/3 {
			ans = append(ans, element2)
		}
		return
	}

	element(nums)


}